package com.atwulidun.idivideandconquer02;

// 问题描述：
// 给出一个长度为n的序列A1,A2,A3·····An，求最大连续和。如序列（-4, 6, -1, 5, 4, -7)，该序列中的最大和是6 +（ - 1）+ 5 + 4 = 14。
// 思路分析：
// 1.划分问题：将序列分成元素个数尽可能相等的两半。
// 2.递归求解：分别求出位于左半和右半的最佳序列。
// 3.合并问题：求出起点位于左半，终点位于右半的最大连续和序列，和子问题最优解比较。
public class ContinuousMaxSum {
    public static void main(String[] args) {
        int[] arr = {-4, 6, -1, 5, 4, -7};
        int max = continuousMaxSum(arr, 0, arr.length - 1);
        System.out.println(max);
    }

    public static int continuousMaxSum(int[] arr, int left, int right) {
        // 划分到只有一个元素的时候
        if (left == right) {
            return arr[left];
        }
        // 1.划分问题
        // 求取中间数
        int mid = left + (right - left) / 2;
        // 2.递归求解
        // 情况一和情况二：当和最大序列完全位于左区间或者位于右区间时
        // 这里出现了一个很严重的问题：左区间的范围应该是left~mid，而不是left~mid-1！！！
        int max = Math.max(continuousMaxSum(arr, left, mid), continuousMaxSum(arr, mid + 1, right));
        // 3.合并问题
        // 情况三：当和最大序列横跨左右两个区间时：
        // 从mid处开始从右往左计算左区间和的最大值；从mid+1处开始从左往右计算右区间和的最大值；左右区间和的最大值加起来就是该种情况和最大值
        int leftMaxSum = arr[mid];
        int leftSum = 0;
        for (int i = mid; i >= left; i--) {
            leftMaxSum = Math.max(leftMaxSum, leftSum += arr[i]);
            // 注意：这里有一个很容易犯的错误：leftSum + arr[i]相当于每次都是0 + arr[i]，需要对leftSum进行赋值更新！！！！！！！！！！
        }
        int rightMaxSum = arr[mid + 1];
        int rightSum = 0;
        for (int i = mid + 1; i <= right; i++) {
            rightMaxSum = Math.max(rightMaxSum, rightSum += arr[i]);
        }
        // 返回三种情况的最大值
        return Math.max(max, leftMaxSum + rightMaxSum);
    }
}
